public class UniqueBinarySearchTrees {
    /*
    * 96. 不同的二叉搜索树
    * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
    *
    * 1 <= n <= 19
    * */
    public static void main(String[] args){

    }

    // 我的想法：第n个二叉搜索树由第n-1个二叉搜索树的种数得来：
    // ......具体怎么得来，没有想出来
    public int mySolution(int n){

        return 0;
    }

    // 按照根节点是啥来分类
    public int numTrees(int n) {
        if(n <= 2)
            return n;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            // 对这个节点数量的情况，以每个值为根节点，遍历一遍
            for (int j = 1; j <= i; j++) {
                // 数量等于左子树的种数 * 右子树的种数
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}
